from typing import List


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        if len(triangle) == 0:
            return 0
        if len(triangle) == 1:
            return triangle[0][0]
        dp = [[]] * len(triangle)
        dp[0] = [triangle[0][0]]
        for i in range(1, len(triangle)):
            dpItem = [0] * len(triangle[i])
            dp[i] = dpItem
            for j in range(len(triangle[i])):
                if j == 0:
                    dp[i][j] = dp[i - 1][j] + triangle[i][j]
                elif j == len(triangle[i]) - 1:
                    dp[i][j] = dp[i - 1][j - 1] + triangle[i][j]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i- 1][j]) + triangle[i][j]

        return min(dp[-1])